package algorithm.swordoff;


/**
 * 数组中的逆序对
 *
 * 核心: 归并排序中合并阶段的逆序对贡献度
 * 遍历后边的数组,计算后面数组每个元素对逆序对的贡献度
 *
 * 贡献度如何理解 - 在归并排序的合并阶段,如
 *
 * 3  8  9  10  +  8  12  15  16
 * i        mid    j
 *
 * 当从前面的数组取数时,i递增,j不变(i和j指向相等时也取前面的i,因为逆序是要严格大于) 直到
 *
 * 3  8  9  10  +  8  12  15  16
 *       i  mid    j
 *
 * 此时i指向比j指向小,i指向的数字开始贡献逆序对数,数量为mid-i+1,也就是前一半数组从i开始到结尾的数量,有这么多个数会比j指向的数字大形成逆序对
 */

public class SQ51 {

    int pairs = 0;

    public int reversePairs(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
        return pairs;
    }

    private void mergeSort(int[] arr, int begin, int end) {
        if (begin < end) {
            int mid = begin + (end-begin)/2;
            mergeSort(arr, begin, mid);
            mergeSort(arr, mid+1, end);
            merge(arr, begin, mid, end);  // 中间一个参数是待合并前一半的末尾
        }
    }

    private void merge(int[] arr, int begin, int mid, int end) {
        int formerIndex = begin, laterIndex = mid+1, i = 0;
        int[] temp = new int[end - begin + 1];

        while (formerIndex <= mid && laterIndex <= end) {
            // 注意相等的时候先取前面数组的,因为题目要求逆序是严格大于
            if (arr[formerIndex] <= arr[laterIndex]) temp[i++] = arr[formerIndex++];
            else {
                pairs += mid - formerIndex + 1;  // 比归并排序多一步
                temp[i++] = arr[laterIndex++];
            }
        }

        while (formerIndex <= mid) temp[i++] = arr[formerIndex++];
        while (laterIndex <= mid) temp[i++] = arr[laterIndex++];

        for (int j = 0; j < i; j++) arr[begin+j] = temp[j];
    }

    public static void main(String[] args) {
        SQ51 sq51 = new SQ51();
        int[] aa = {1,3,2,3,1};
        System.out.println(sq51.reversePairs(aa));

    }


}
